﻿
@{
    ViewBag.Title = "Index";
    Layout = "~/Views/Shared/_Layout.cshtml";
    string[,] str =
    {   // 名称，方法
        { "前言","t"},
        {"桶排序","BucketSort" },
        {"冒泡排序","BubbleSort" },
        {"快速排序*","QuickSort" }
    };
    int index = 1;
}

<div class="layui-tab layui-tab-brief">
    <ul class="layui-tab-title title-pin">
        @{
            for (int i = 0; i < str.Length / 2; i++) {
                <li class="@(i==0?"layui-this":"")">@str[i, 0]</li>
            }
        }
    </ul>
    <div class="layui-tab-content">
        <!-- 前言 -->
        <div class="layui-tab-item layui-show">
            <blockquote class="layui-elem-quote ">
                <p>存 在 数 组 ：3，9，2，5，5，7，9</p>
                <p>稳 定 排 序 ：两个5不会交换位置</p>
                <p>不稳定排序：两个5可能交换位置</p>
                <p>优 缺 举 例 ：假如发奖学金，排在前三个的有奖，结果一排序把原来在第三位的并列第三名给弄到第四位了，他估计不会乐意</p>
            </blockquote>
            @*<pre class="layui-code code" lay-title="C#">
                @ViewBag.Sort
                </pre>*@
        </div>
        <!-- 桶排序 -->
        <div class="layui-tab-item">
            <blockquote class="layui-elem-quote">
                <p>优点：非常快，简单</p>
                <p>缺点：消耗空间，无法处理小数，仅仅只能排序，不稳定</p>
                <p>时间复杂度： O(M+N)</p>
            </blockquote>
            <blockquote class="layui-elem-quote layui-quote-nm">
                <b>思路：</b>
                建立长度为合适的数组，每出现一个数字，对应索引加一，最后顺序输出数组
            </blockquote>

            @* 测试文本框 *@
            @Html.Partial("_Input",
           new ViewDataDictionary { { "Url", Url.Action(str[index++, 1], "Sort") }, { "Title", "排序" }, { "Des", "+，[100,900]" } })

<pre class="layui-code code" lay-title="C#">
        /// <summary>
        /// 桶排序
        /// </summary>
        /// <param name="arr">带排序数组< /param>
        /// <param name="min">最小值< /param>
        /// <param name="max">最大值< /param>
        /// <returns></returns>
        public int[] BucketSort(double[] arr, int min, int max) {
            // 准备桶
            int[] num = new int[max - min + 1];
            // 差值为：  (最小值)100-(初始索引)0=100
            int diff = min - 0;
            List< int> list = new List< int>();

            // 开始排序
            for (int i = 0; i < arr.Length; i++) {
                // 满足条件，[100,900]
                if (min <= arr[i] && arr[i] <= max) {
                    // 对应索引加一，索引对应的值，表示当前数字出现的次数
                    num[(int)arr[i] - diff]++;
                }
            }
            // 输出
            for (int i = 0; i < num.Length; i++) {
                // 当 num[i] 为0时，表示 i 没有出现过
                if (num[i] <= 0) continue;
                // 输出 num[i] 个 i
                for (int j = 0; j < num[i]; j++)
                    list.Add(i + diff);
            }
            return list.ToArray();
        }
      </pre>
        </div>
        <!-- 冒泡排序 -->
        <div class="layui-tab-item ">
            <blockquote class="layui-elem-quote ">
                <p>优点：适用广泛，稳定</p>
                <p>缺点：较慢，时间复杂度高</p>
                <p>时间复杂度：O(N<sup>2</sup>)</p>
            </blockquote>
            <blockquote class="layui-elem-quote layui-quote-nm layui-row">
                <b>思路：</b>

                取第一个依次与第二、三、四...个比较（第一个循环），每次比较时，判断哪个数更小，较小数放置第一位，全部比较完毕后为“一趟”<br />

                然后取第二个，继续依次与第三、四...个比较（第二个循环）

            </blockquote>

            @* 测试文本框 *@
            @Html.Partial("_Input",
           new ViewDataDictionary { { "Url", Url.Action(str[index++, 1], "Sort") }, { "Title", "排序" } })

            <!--代码块-->
<pre class="layui-code code" lay-title="C#">
        /// <summary>
        /// 冒泡排序
        /// </summary>
        /// <param name="arr">待排序数组< /param>
        /// <returns></returns>
        public static double[] BubbleSort(double[] arr) {

            // 依次获取未排序的数字，最后一个不获取
            for (int i = 0; i < arr.Length - 1; i++) {
                // 循环获取未排序数字之后的数字
                for (int j = i + 1; j < arr.Length; j++) {
                    if (arr[i] > arr[j]) {
                        // 交换两个数字
                        arr[i] += arr[j];
                        arr[j] = arr[i] - arr[j];
                        arr[i] = arr[i] - arr[j];
                    }
                }
            }
            return arr;
        }
      </pre>
        </div>
        <!-- 快速排序 -->
        <div class="layui-tab-item ">
            <blockquote class="layui-elem-quote ">
                <p>优点：冒泡排序优化，最常用，排序更快</p>
                <p>缺点：不稳定</p>
                <p>时间复杂度：O (N<i>log</i>N)</p>
            </blockquote>
            <blockquote class="layui-elem-quote layui-quote-nm layui-row">
                <b>思路：</b>

                取一个参考值（k），将数组中，比k小的数字放在k的左边，比k大的数字放在k的右边（第一个循环）<br />

                然后分别让k左边和k右边的数组重复第一步（第二个循环）

            </blockquote>

            @* 测试文本框 *@
            @Html.Partial("_Input",
           new ViewDataDictionary { { "Url", Url.Action(str[index++, 1], "Sort") }, { "Title", "排序" } })

            <!--代码块-->
<pre class="layui-code code" lay-title="C#">
        /// <summary>
        /// 快速排序
        /// </summary>
        /// <param name="arr">待排序数组< /param>
        /// <param name="start">开始索引< /param>
        /// <param name="end">结束索引< /param>
        /// <returns></returns>
        public static double[] Quicksort(double[] arr, int start = -1, int end = -1) {

            // 递归退出条件
            if (start != -1 & start != -1) {
                if (start < 0 || arr.Length <= start)
                    return arr;
                if (end < 0 || arr.Length <= end)
                    return arr;
                if (end <= start)
                    return arr;
            }

            // 初始化值
            if (start == -1)
                start = 0;
            if (end == -1)
                end = arr.Length - 1;

            int i = start;
            int j = end;

            // 随机获取参考值
            Random ran = new Random();
            double k = arr[ran.Next(start, end + 1)];

            // 从后向前找
            for (; i < j; j--) {
                // 当后面的数小于参考值时
                if (arr[j] <= k) {
                    // 从前向后找
                    for (; i < j; i++) {
                        // 当前面的数大于参考值时
                        if (k <= arr[i]) {
                            // 交换前后值
                            arr[i] += arr[j];
                            arr[j] = arr[i] - arr[j];
                            arr[i] = arr[i] - arr[j];
                            break;
                        }
                    }
                }
            }

            // 排序右边数组
            arr = Quicksort(arr, start, i - 1);
            // 排序左边数组
            arr = Quicksort(arr, i + 1, end);

            return arr;
        }
      </pre>
        </div>
    </div>
</div>


